package main

import "fmt"

// 自底向上归并排序
func mergeSort2(array []int, begin, end int) {
	// 步数为1开始，step长度的数组表示一个有序的数组
	step := 1

	for end-begin > step {
		// 从头到尾对数组进行归并操作
		// step << 1 = 2 * step 表示偏移到后两个有序数组将它们进行归并
		for i := begin; i < end; i += step << 1 {
			var lo = i                // 第一个有序数组的上界
			var mid = lo + step       // 第一个有序数组的下界，第二个有序数组的上界
			var hi = lo + (step << 1) // 第二个有序数组的下界

			// 不存在第二个数组，直接返回
			if mid > end {
				return
			}

			// 第二个数组长度不够
			if hi > end {
				hi = end
			}

			merge2(array, lo, mid, hi)
		}

		// 上面的 step 长度的两个数组都归并成一个数组了，现在步长翻倍
		step <<= 1
	}
}

// 归并操作
func merge2(array []int, begin int, mid int, end int) {
	// 申请额外的空间来合并两个有序数组，这两个数组是 array[begin,mid),array[mid,end)
	lSize := mid - begin     // 左边数组的长度
	rSize := end - mid       // 右边数组的长度
	newSize := lSize + rSize // 辅助数组的长度
	result := make([]int, 0, newSize)

	l, r := 0, 0
	for l < lSize && r < rSize {
		lValue := array[begin+l] // 左边数组的元素
		rValue := array[mid+r]   // 右边数组的元素
		if lValue < rValue {
			result = append(result, lValue)
			l++
		} else {
			result = append(result, rValue)
			r++
		}
	}
	// 将剩下的元素追加到辅助数组后面
	result = append(result, array[begin+l:mid]...)
	result = append(result, array[mid+r:end]...)

	// 将辅助数组的元素复制回原数组，这样该辅助空间就可以被释放掉
	for i := 0; i < newSize; i++ {
		array[begin+i] = result[i]
	}
	return
}

func main() {
	list := []int{5}
	mergeSort2(list, 0, len(list))
	fmt.Println(list)

	list1 := []int{5, 9}
	mergeSort2(list1, 0, len(list1))
	fmt.Println(list1)

	list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	mergeSort2(list2, 0, len(list2))
	fmt.Println(list2)
}
